Bluetooth is a wireless protocol intended for short-range communication between devices. One aspect of the Bluetooth protocol is the Bluetooth Secure Simple Pairing (BT-SSP) protocol. The BT-SSP is intended to provide a secure mechanism for pairing between two Bluetooth devices. According to the protocol each device has a public-private key pair. In the first step of the BT-SSP protocol the devices exchange their public keys. Then each device computes its own Diffie-Hellman key (DHKey) as a function of its private key and the other device's public key. That DHKey is then used to compute a so-called MAC Ea value that is sent to the other device in the ninth step of the BT-SSP protocol. Crucial to the protocol is that the private key of any device must be kept secret. Otherwise, the device could be vulnerable to attack.
The BT-SSP protocol uses an elliptic curve Diffie-Hellman (ECDH) algorithm. The elliptic curve E used in the protocol can be expressed by its parameters as E=(a,b,p,r). The curve is defined over the integers modulo p (which will be denoted Zp herein) with Γ points on the curve, the points being given by the equation y2=x3+ax+b, where p and r are both primes.
In September 2006 an attack against the BT-SSP protocol known as the “invalid curve attack” came to light. The invalid curve attack is intended to reveal the private key of a Bluetooth device. The attack operates as follows.
Suppose an attacker wants to use a device B to attack a device A and discover the private key of device A. The attacker selects an invalid public key composed of data that constitutes the coordinates of a point lying on an invalid curve (i.e. a curve that does not satisfy the conditions detailed above for E) with smaller order. The attacker then configures device B to use that key for executing the ECDH part of the BT-SSP protocol with device A. In accordance with the BT-SSP protocol, device A computes a DHKey using an invalid point (PKb) received from B and its own private key (SKa), and then uses that DHKey in order to calculate the Ea in step 9 of the BT-SSP protocol and sends that Ea to device B. Once the attacker knows that Ea, and with knowledge of the invalid public key PKb that was used in generating it B can recover a part of the private key SKa of A. By repeating this procedure, B can eventually recover the full private key of A using the Chinese Remainder Theorem.
Once an attacker knows the private key SKa used for ECDH of a device A, it may be possible for the attacker to derive all further link keys used by A. This is because the Bluetooth specification has not required device A to refresh its ECDH key pair. [See the Bluetooth 2.1+EDR core specification, 26th Jul. 2007, Vol. 2 part H 7.1 Phase 1: Public Key Exchange”]. This means that an attacker who knows SKa, can—assuming SKa has not been refreshed by device A—compute any further DHKey. This extends even to DHKeys used for communication with third devices because their public keys (PKb) will be communicated to device A in clear text. From this the attacker can also compute the link key LK because all the other input parameters to the function f2 used in phase 4 of the BT-SSP protocol (nonces and BD_ADDR device addresses) are also passed in clear text.
Three options have been proposed to allow a device to protect its private key against attacks that use invalid public keys. Those are:
1. The invalid curve attack is not practically feasible when the attacked device (A) frequently refreshes its private ECDH key SKa. Therefore, to protect against the attack the device could change its private key after a number of successful or failed attempts to pair from any single BD_ADDR device address, or at some other relatively frequent interval. This approach has some drawbacks. First, one of the authentication mechanisms provided for in the BT-SSP protocol uses data transferred out of band (i.e. other than via Bluetooth), for example by near field communication (NFC). Some of the information that is exchanged out of band is a function of the private key. An example of this configuration is a Bluetooth headset that incorporates a passive NFC tag that is static (i.e. its content cannot be changed) and programmed in the factory when the headset is made. This tag is then used to introduce and secure the link between a headset and phone. If the headset were to change its keys at any point after the tag has been created (as would be involved if it implemented this first method of protection from the invalid curve attack) then the NFC tag would subsequently be useless. Second, this method of protection requires persistent counters to be kept in memory, for example in flash or EEPROM. Both of these memory technologies have a limited number of guaranteed writes. This could lead to an attack on a device which shortens its life. This could be solved by using a different key for every pairing attempt, but this would be costly in CPU time.
2. The invalid curve attack relies on the injection of an invalid public key as input for device A to compute its DHKey. Therefore, the device could verify that any received public key on the basis of which it is requested to compute a DHKey lies on the correct curve, and if it does not then the device could reject that request. One way to check the validity of a public key Q received from another device is as follows:                a. verify that the input point represented by Q is not equal to the point at infinity;        b. verify that the x and y coordinates represented by Q are properly represented elements of the field;        c. verify that Q lies on the valid elliptic curve.If any of these tests is not satisfied then the device A rejects the request to generate a DHKey. Techniques of this nature are discussed in WO 99/20020, U.S. Pat. Nos. 6,563,928, 5,933,504, EP 0 743 774 and EP 1 025 672.        
3. The device could implement elliptic curve point addition and doubling by means of mechanisms that are valid only on the correct curve so that an error automatically arises if the device tries to compute a DHKey from an public key that lies on an invalid curve.
Further mechanisms to protect against the invalid curve attack, and potentially other similar attacks, would be desirable since they could increase security and could be more efficient than the existing mechanisms.